import java.util.ArrayList;

public class question_57 {
}
class Solution_57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals==null||intervals.length==0){
            return new int[][]{newInterval};
        }
        if(newInterval==null||newInterval.length==0){
            return intervals;
        }
        ArrayList<int[]> result=new ArrayList<>();
        ArrayList<int[]> temp=new ArrayList<>();
        int sum=0;
        for (int[] t:intervals){//这样的话就省去了排序的功夫，因为给你的intervals数组本身就是有序的了
            if(t[0]>=newInterval[0]&&sum==0){
                temp.add(newInterval);
                temp.add(t);
                sum++;
            }else{
                temp.add(t);
            }
        }
        if(sum==0)//说明newinterval根本还没加进去，也就是说根据大小排序之后这个新加入的应该是加在最后一个的，所以
            temp.add(newInterval);
        int t[]=new int[2];
        t[0]=temp.get(0)[0];
        t[1]=temp.get(0)[1];
        for (int[] a:temp){
            if(a[0]>t[1]){
                int temp1[]=new int[2];
                temp1[0]=t[0];
                temp1[1]=t[1];
                result.add(temp1);
                t[0]=a[0];
                t[1]=a[1];
            }else{
                t[1]=t[1]>a[1]?t[1]:a[1];
            }
        }
        //别忘记了最后一个
        result.add(t);
        return result.toArray(new int[result.size()][2]);
    }
}
